package org.example.myleet.p1202;

import java.util.*;

public class Solution {
    /**
     * 54 ms
     * 使用路径压缩的并查集找到所有连通的交换位置，并将这些交换位置中的字符按照字典序升序排序摆放得到结果
     */
    public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
        PathCompressedUnionFind unionFind = new PathCompressedUnionFind(s.length());
        //对连通索引构建路径压缩的并查集
        for (List<Integer> pair : pairs) {
            unionFind.union(pair.get(0), pair.get(1));
        }
        //找出每个集合的字母对应的代表元
        Map<Integer, PriorityQueue<Character>> rootCharsMap = new HashMap<>();
        for (int i=0;i<s.length();i++) {
            //找到该位置在并查集中的代表元
            int root = unionFind.find(i);
            //根据代表元，在相应的字符集添加到这个代表元的大顶堆中
            rootCharsMap.computeIfAbsent(root, key -> new PriorityQueue<>()).offer(s.charAt(i));
        }
        //将每个片段的字符集和按照位置集顺序拼接起来得到结果
        char[] result = new char[s.length()];
        for (int i=0; i<s.length(); i++) {
            int root = unionFind.find(i);
            //直接从大顶堆中弹出元素拼接到结果中
            PriorityQueue<Character> chars = rootCharsMap.get(root);
            Character c = chars.poll();
            if (c != null) {
                result[i] = c;
            }
        }
        return new String(result);
    }

    static class PathCompressedUnionFind {
        int[] parent;
        int[] rank;

        public PathCompressedUnionFind(int len) {
            parent = new int[len];
            for (int i=0; i<parent.length; i++) {
                parent[i] = i;
            }
            rank = new int[len];
        }

        public void union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX == rootY) {
                return;
            }
            if (rank[rootX] == rank[rootY]) {
                parent[rootX] = rootY;
                //相同层级的情况下将其中一侧的节点提升一个高度，之后再合并的节点或子数都将会以这个更高的节点为中心
                rank[rootY]++;
            } else if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else {
                parent[rootY] = rootX;
            }
        }

        public int find(int i) {
            if (parent[i] != i) {
                parent[i] = find(parent[i]);
            }
            return parent[i];
        }
    }
}
